Crate crossbeam_deque

A concurrent work-stealing deque.

This data structure is most commonly used in schedulers. The typical setup involves a number of threads where each thread has its own deque containing tasks. A thread may push tasks into its deque as well as pop tasks from it. Once it runs out of tasks, it may steal some from other threads to help complete tasks more quickly. Therefore, work-stealing deques supports three essential operations: push, pop, and steal.

Types of deques

There are two types of deques, differing only in which order tasks get pushed and popped. The two task ordering strategies are:

• First-in first-out (FIFO)
• Last-in first-out (LIFO)

A deque is a buffer with two ends, front and back. In a FIFO deque, tasks are pushed into the back, popped from the front, and stolen from the front. However, in a LIFO deque, tasks are popped from the back instead - that is the only difference.

Workers and stealers

There are two functions that construct a deque: fifo and lifo. These functions return a Worker and a Stealer. The thread which owns the deque is usually called worker, while all other threads are stealers.

Worker is able to push and pop tasks. It cannot be shared among multiple threads - only one thread owns it.

Stealer can only steal tasks. It can be shared among multiple threads by reference or by cloning. Cloning a Stealer simply creates another one associated with the same deque.

Examples

use crossbeam_deque as deque;
use std::thread;

// Create a LIFO deque.
let (w, s) = deque::lifo();

// Push several elements into the back.
w.push(1);
w.push(2);
w.push(3);

// This is a LIFO deque, which means an element is popped from the back.
// If it was a FIFO deque, `w.pop()` would return `Some(1)`.
assert_eq!(w.pop(), Some(3));

// Create a stealer thread.
thread::spawn(move || {
    assert_eq!(s.steal(), Some(1));
    assert_eq!(s.steal(), Some(2));
}).join().unwrap();

Structs

Stealer	The stealer side of a deque.
Worker	The worker side of a deque.

Functions

fifo	Creates a work-stealing deque with the first-in first-out strategy.
lifo	Creates a work-stealing deque with the last-in first-out strategy.